1. Field of the Invention
The present invention relates generally to data error detection and correction, and more particularly to a system and method of generating low density parity check (LDPC) codes using a bit filling technique.
2. Description of the Related Art
It is well known that the probability of errors in digital data transmission increases as the signal-to-noise ratio worsens. Since it is not always practical to reduce noise in the transmission path, techniques for dealing with errors in a received signal have been developed. Many of these techniques, referred to as error control codes, involve the transmission of redundant digits, which do not themselves convey information but make it possible for errors to be controlled at the receiver. Some error control codes detect errors and some detect and correct errors.
One class of error correction codes (ECCs) that both detect and correct errors is known as the xe2x80x9cHamming Codesxe2x80x9d, which are widely used for error detection and correction in digital communications data storage systems. The Hamming Codes are capable of detecting multiple bit errors and correcting single bit errors. Another well known ECC algorithm is the xe2x80x9cReed-Solomon codexe2x80x9d, widely used for error correction in the compact disk industry. The Reed-Solomon code is able to correct multiple errors per word. Other conventional ECC algorithms include the xe2x80x9cb-adjacentxe2x80x9d error correction code, and the xe2x80x9codd weight columnxe2x80x9d code.
One example of an application of an error correction technique commonly used for computer memory systems is known as a Redundant Array of Independent Disks (RAID), wherein a number of small disk drives are used to store data with the data being spread across a number of the disk drives. When data is received from a host computer by a RAID controller, it typically arrives in 8-bit byte form, with a ninth, parity bit for each byte. The controller writes the data across a number of disks, putting different blocks of data in different disks. As the RAID controller writes the data it will typically generate a check code, such as a Cyclic Redundancy Check (CRC). This is basically an exclusive OR (XOR) of each bit position in successive bytes throughout a sector. Another example is linear parity, which is an exclusive OR function of successive words of any convenient length. The aforementioned Reed Solomon codes may also be used in RAID systems.
In addition to these check codes, the RAID controller also provides a parity calculation. The parity is the exclusive OR of the data blocks in each disk drive, with the exclusive OR being a parity block which is stored on a separate parity disk. The parity calculation is usually done not only on the data itself, but also on the check codes, which are stored with the data on each disk drive.
One type of error correction utilizes Low Density Parity Check (LDPC) Codes, which were first introduced in 1963. Initial approaches of designing LDPC codes used a construction that had a fixed weight for all the columns of the parity-check matrix. Recently, it has been shown that LDPC codes can perform very close to the Shannon capacity limit when their associated Tanner graphs posses certain desirable properties. Tanner graphs are bipartite graphs that can be used to represent a parity check matrix of LDPC codes. One desirable property is that Tanner graphs have a large xe2x80x9cgirthxe2x80x9d, which is the smallest cycle in the graph. This is important because when decoding LDPC codes using the sum-product decoding algorithm, the number of independent iterations of the algorithm is proportional to the girth of the Tanner graph corresponding to the code. Another desirable property is high xe2x80x9cratexe2x80x9d. For a code with a parity check matrix having m rows and n columns, the rate, R, is given by   R  =                    (                  n          -          m                )            n        .  
U.S. Pat. Nos. 4,295,218 and 3,542,756, both of which are incorporated herein by reference, disclose decoding methods with which the present invention can be used.
Various recent approaches to designing LDPC codes include the use of a fixed girth parity check matrix with a random construction, the design of irregular graphs using random constructions and linear programming, as well as the design of LDPC codes using either array codes, Steiner designs or finite geometries.
The above-discussed techniques for designing LDPC codes typically have exponential time complexity. As a result, they can only be made to work for small parity check column weights and for small girth values. Also, the prior techniques also do not usually yield a satisfactorily high rate. Furthermore, these techniques do not offer sufficient flexibility to permit one to choose codes with certain fixed values, such as girth, and then design the codes with various other desirable parameters optimized. As a result, using conventional techniques cannot choose to trade-off, for example, bit error rate performance against the code rate. An added feature of our technique is that cycles are only formed if necessary. The algorithm starts out using a large girth constraint, , and then decreases the girth constraint as needed throughout the execution of the algorithm. As a result, the girth is always as high as possible, and the number of short cycles formed is small.
The present invention has carefully considered the above problems and has provided the solution set forth herein.
A computer-implemented system and method is disclosed for generating low-density parity check (LDPC) codes. One aspect of the invention includes a method for generating high rate LDPC codes that first constructs a matrix (H) of size mxc3x97n having m rows of check nodes and n columns of bit nodes. The matrix meets the following requirements: the weight of the jth column equals aj; each row, r, has weight at most br; and the matrix H can be represented by a Tanner graph that has a girth gxe2x89xa7g. The method then iteratively adds an (n+1)th column (U1) to matrix H, wherein the size of U1 g is initially empty and is at most an+1, and wherein U1 comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than an+1. The method then iteratively adds check nodes to U1 such that each check node does not violate predetermined girth and check-degree constraints. The matrix H is updated when a new column is added. The iterations are terminated if there are no new check nodes that do not violate the girth and check-degree constraints. The method can be modified to optimize various parameters, including the following cases: maximizing the rate for a fixed girth; maximizing the girth for a fixed rate; and maximizing the rate for a fixed girth and fixed length.
In accordance with another aspect of the invention an LDPC code generator is provided for creating LDPC codes for use in an LDPC error correcting system that includes an LDPC encoder that receives digital data and encodes said data using the LDPC codes. The LDPC code generator includes a unit for generating an mxc3x97n matrix (H) having m rows of check nodes and n columns of bit nodes, wherein the weight of the jth column is aj, each row, r, has weight at most br, and wherein the matrix H can be represented by a Tanner graph that has a girth of at least gxe2x89xa7g. The LDPC code generator also includes a processing module for iteratively adding (n+1)th columns (U1) to matrix H, wherein the size of U1 is initially empty and is at most an+1, and wherein U1 comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than an+1. Another processing module iteratively adds check nodes to U1 such that each check node does not violate predetermined girth and check-degree constraints. An additional processing module updates matrix H when a new column is added and another processing module terminates the iterations if there are no new check nodes that do not violate the girth and check-degree constraints, or if the desired number of bit nodes has been added.
The details of the present invention, both as to its structure and operation, can best be understood in reference to the accompanying drawings, in which like reference numerals refer to like parts, and in which: